package org.sample.algorithm.sort;

public class QuickSort {

    public static int[] sort(int[] array) {
        sort(array, 0, array.length - 1);
        return array;
    }

    private static void sort(int[] array, int low, int high) {
        if (low < high) {
            int mid = sortUnit(array, low, high);
            sort(array, low, mid - 1);
            sort(array, mid + 1, high);
        }
    }

    private static int sortUnit(int[] array, int low, int high) {
        int k = array[low];
        while (low < high) {
            while (k <= array[high] && low < high)
                high--;
            array[low] = array[high];
            while (k >= array[low] && low < high)
                low++;
            array[high] = array[low];
        }
        array[low] = k;
        return low;
    }

}